#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bsHeap.h"


typedef struct _bs_element_t
{
    void* data; // 存储数据
}BS_ELEMENT_t;

typedef struct _bs_heap_body_t
{
    E_CMP_t (*compare)(void* d1, void* d2);  // d1 < d2 返回 E_CMP_LESS，  d1 == d2 返回 E_CMP_EQUAL, d1 > d2 返回 E_CMP_GREATER
    int cap;                // 当前容量
    int len;                // 当前储存数据个数
    int max;                // 最大容量
    BS_ELEMENT_t element[];
}BS_HEAP_BODY_t;

static BS_HEAP_BODY_t* bsHeapGetBody(BS_HEAP_t* bsHeap)
{
    if (NULL == bsHeap)
        return NULL;
    return (BS_HEAP_BODY_t*)(bsHeap->body);
}


static void bsHeapDataSwap(BS_ELEMENT_t* d1, BS_ELEMENT_t* d2)
{
    BS_ELEMENT_t temp = *d1;
    *d1 = *d2;
    *d2 = temp;
}

// 添加元素时维护二叉堆向上浮动，从最后一个元素向上浮动，直到不小于父节点或者到堆顶
static void bsHeapFlowUp(BS_HEAP_t* bsHeap)
{
    BS_HEAP_BODY_t* body = bsHeapGetBody(bsHeap);
    if(NULL == body)
        return;

    if(body->len <= 1) return;

    int now = body->len;// 从最后一个元素开始
    
    while(now) // 找到堆顶退出循环
    {
        if(body->compare(body->element[now].data, body->element[now/2].data) == E_CMP_LESS) // 当前元素小于父节点则交换
        {
            bsHeapDataSwap(&body->element[now], &body->element[now/2]);
            now = now/2;
        }else break; // 大于等于父节点退出循环
    }
}


// 删除元素时维护二叉堆向下浮动，先把指定元素和最后一个元素交换位置，然后从删除位置向下浮动
static void bsHeapFlowDown(BS_HEAP_t* bsHeap, int pos)
{
    BS_HEAP_BODY_t* body = bsHeapGetBody(bsHeap);
    if(NULL == body)
       return;
    if(pos < 1) 
        return;
    
    int now = pos * 2; // 删除位置的左孩子
    int father = pos;
   
    bsHeapDataSwap(&body->element[pos], &body->element[body->len]);// 先交换要删除的元素和最后一个元素
    while(now < body->len)// 找到最后一个元素时结束
    {
   	    // 比较左孩子和右孩子找到比较小的那个
        if((now + 1) < body->len && body->compare(body->element[now].data, body->element[now + 1].data) == E_CMP_GREATER)
           now ++;

       	// 若大于较小的子节点则交换
        if( body->compare(body->element[father].data, body->element[now].data) == E_CMP_GREATER)
        {
            bsHeapDataSwap(&body->element[father], &body->element[now]);
        }
        else 
            break;// 小于等于较小的子节点时推出循环

        father = now;
        now = now * 2;
    }
}

// 添加元素，元素数组从 1 位置开始， 0 不用
static int bsHeapAdd(BS_HEAP_t* bsHeap, void* input, int len)
{
    BS_HEAP_BODY_t* body = bsHeapGetBody(bsHeap);
    if(NULL == body)
        return -1;

    if (body->len  >= body->cap - 1)
    {
    	// 容量不足扩充容量
        int newCap = body->cap + body->cap/3;
        if(newCap > body->max)
            return -4;
        body->cap = newCap;
          
        void* temp = realloc(bsHeap->body, sizeof(BS_HEAP_BODY_t) + sizeof(BS_ELEMENT_t) * (body->cap + 1));
        if(NULL == temp)
        {
            return -2;
        }

        bsHeap->body =  temp;
        body = bsHeapGetBody(bsHeap);
        memset(&body->element[body->len + 1], 0,  (body->cap - body->len - 1) * sizeof(BS_ELEMENT_t));
    }

    body->len++;
    body->element[body->len].data = malloc(len);

    if(NULL == body->element[body->len].data)
    {
        body->len--;
        return -3;
    }

    memset(body->element[body->len].data, 0, len);
    memcpy(body->element[body->len].data, input, len);    

    if(body->len > 1)
    {
        bsHeapFlowUp(bsHeap);
    }

    return 0;
}

static void* bsHeapPop(BS_HEAP_t* bsHeap)
{
    BS_HEAP_BODY_t* body = bsHeapGetBody(bsHeap);
    
    if(NULL == body)
        return NULL;

    void* res = body->element[1].data;

    // 这里要弹出堆顶，从 1 开始
    bsHeapFlowDown(bsHeap, 1);

    // 清除最后一个元素
    memset(&body->element[body->len], 0, sizeof(BS_ELEMENT_t));

    body->len--;

    return res;
}


static void bsHeapDestruct(BS_HEAP_t** pBsHeap)
{
    BS_HEAP_t* bsHeap = *pBsHeap;

    if(NULL == bsHeap)
        return;

    BS_HEAP_BODY_t* body = bsHeapGetBody(bsHeap);
    
    if(NULL != body)
    {
        for(int i = 1; i <= body->len; i++)
        {
            free(body->element[i].data);
        }
        free(body);
    }
    free(bsHeap);

    *pBsHeap = NULL;
}

BS_HEAP_t* bsHeapCreate(int cap, int max, E_CMP_t(*cmp)(void*, void*))
{
    BS_HEAP_t* bsHeap = (BS_HEAP_t*)malloc(sizeof(BS_HEAP_t));
    if(NULL == bsHeap)
    {
        return NULL;
    }

    memset(bsHeap, 0, sizeof(BS_HEAP_t));

    bsHeap->body = malloc(sizeof(BS_HEAP_BODY_t) + sizeof(BS_ELEMENT_t) * (cap + 1));

    if(NULL == bsHeap->body)
    {
        free(bsHeap);
        return NULL;
    }
    memset(bsHeap->body, 0, sizeof(BS_HEAP_BODY_t) + sizeof(BS_ELEMENT_t) * (cap + 1));

    bsHeap->add = bsHeapAdd;
    bsHeap->pop = bsHeapPop;
    bsHeap->destruct = bsHeapDestruct;

    BS_HEAP_BODY_t* body = bsHeapGetBody(bsHeap);
    body->cap = cap;
    body->max = max;
    body->compare = cmp;
    
    return bsHeap;
}
